<html>
<head>
  <title>Deep Q Network (DQN)</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="767"/>
<h1>Deep Q Network (DQN)</h1>

<div>
<span><div><div><span style="font-size: 18pt; color: rgb(28, 51, 135); line-height: 1.45;">1. 强化学习和深度学习结合</span></div><div><font style="font-size: 12pt;"><span style="color: rgb(173, 0, 0); font-size: 12pt; font-weight: bold;"> 机器学习=目标+表示+优化。</span></font></div><div><ul><li><span style="line-height: 1.45;">目标层面的工作关心应该学习到什么样的模型，强化学习应该学习到使得激励函数最大的模型。</span></li><li><span style="line-height: 1.45;">表示方面的工作关心数据表示成什么样有利于学习，深度学习是最近几年兴起的表示方法，在图像和语音的表示方面有很好的效果。</span></li><li><span style="line-height: 1.45;">深度强化学习则是两者结合在一起，深度学习负责表示马尔科夫决策过程的状态，强化学习负责把控学习方向。</span></li></ul></div><div><br/></div><div>深度强化学习有三条线：</div><div><ul><li><span style="line-height: 1.45;">基于价值的深度强化学习</span></li><li><span style="line-height: 1.45;">基于策略的深度强化学习</span></li><li><span style="line-height: 1.45;">基于模型的深度强化学习</span></li></ul><div><span style="line-height: 1.45;">这三种不同类型的深度强化学习</span><font style="font-size: 12pt;"><span style="line-height: 1.45; color: rgb(173, 0, 0); font-size: 12pt; font-weight: bold;">用深度神经网络替代了强化学习的不同部件</span></font><span style="line-height: 1.45;">。基于价值的深度强化学习本质上是一个 Q Learning 算法，目标是估计最优策略的 Q 值。 不同的地方在于 Q Learning 中价值函数近似用了深度神经网络。比如 DQN 在 Atari 游戏任务中，输入是 Atari 的游戏画面，因此使用适合图像处理的卷积神经网络（Convolutional Neural Network，CNN）。下图就是 DQN 的框架图。</span></div></div><div><a href="http://www.algorithmdog.com/wp-content/uploads/2016/09/dqn-atari.png"><img src="Deep Q Network (DQN)_files/Image.png" type="image/png" data-filename="Image.png" width="509"/></a></div><div><br/></div><div><br/></div><h3><span style="color: rgb(28, 51, 135); font-size: 18pt;">2. Deep Q Network (DQN) 算法</span></h3><div>        这个算法就是著名的 DQN 算法，由 DeepMind 在 2013 年在 NIPS 提出。DQN 算法的主要做法是 <font style="font-size: 12pt;"><span style="color: rgb(173, 0, 0); font-size: 12pt; font-weight: bold;">Experience Replay</span></font>，其将<font style="font-size: 12pt;"><span style="color: rgb(173, 0, 0); font-size: 12pt; font-weight: bold;">系统探索环境</span></font>得到的数据储存起来，然后<font style="font-size: 12pt;"><span style="color: rgb(173, 0, 0); font-size: 12pt; font-weight: bold;">随机采样样本更新深度神经网络的参数</span></font>。</div><div><img src="Deep Q Network (DQN)_files/Image [1].png" type="image/png" data-filename="Image.png"/></div><div><font style="font-size: 24pt; color: rgb(50, 135, 18);"><b>理解：世上本没有action，两个state之间的不同便成了action</b></font></div><div style="text-align: center;"><br/></div><div style="text-align: center;"><br/></div><div style="text-align: left;"><br/></div><div style="text-align: left;">We can put the state diagram and the instant reward values into the following <font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>reward table, &quot;matrix R&quot;</b></font>.<br/></div><div style="text-align: center;"><img src="Deep Q Network (DQN)_files/Image.gif" type="image/gif" data-filename="Image.gif" width="346"/>       <img src="Deep Q Network (DQN)_files/Image [1].gif" type="image/gif" data-filename="Image.gif" width="304"/></div><div>The -1's in the table represent null values (i.e.; where there isn't a link between nodes). For example, State 0 cannot go to State 1.</div><div><br/></div><div><br/></div><div>Now we'll add a similar matrix, &quot;Q&quot;, to the brain of our agent, representing the memory of what the agent has learned through experience.  The rows of matrix Q represent the current state of the agent, and the columns represent the possible actions leading to the next state (the links between the nodes).</div><div><br/></div><div><br/></div><div><font style="font-size: 12pt; color: rgb(173, 0, 0);"><b>The agent starts out knowing nothing, the matrix Q is initialized to zero.  In this example, for the simplicity of explanation, we assume the number of states is known (to be six).  If we didn't know how many states were involved, the matrix Q could start out with only one element.  It is a simple task to add more columns and rows in matrix Q if a new state is found.</b></font></div><div><br/></div><div><span style="-en-paragraph: true;">The transition rule of Q learning is a very simple formula:</span></div><blockquote><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;">Q(state, <font style="font-size: 12pt;"><b>action</b></font>) = R(state, <font style="font-size: 12pt;"><b>action</b></font>) + Gamma * Max<span style="-en-paragraph: true; font-size: 18px;">[</span>Q(<font style="font-size: 12pt;"><b>next state</b></font>, all actions)<span style="-en-paragraph: true; font-size: 18px;">]</span></div></blockquote><div><span style="-en-paragraph: true;">According to this formula, a value assigned to a specific element of matrix Q, is equal to the sum of the corresponding value in matrix R and the learning parameter Gamma, multiplied by the maximum value of Q for all possible actions in the next state.</span></div><div><span style="-en-paragraph: true;"> </span></div><div>Our virtual agent will learn through experience, without a teacher (this is called unsupervised learning).  The agent will explore from state to state until it reaches the goal. We'll call each exploration an episode.  Each episode consists of the agent moving from the initial state to the goal state.  Each time the agent arrives at the goal state, the program goes to the next episode.</div><div><br/></div><div><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><b>The Q-Learning algorithm goes as follows:</b></font></span></div><blockquote><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><b>1. Set the gamma parameter, and environment rewards in matrix R.</b></font></span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><b>2. Initialize matrix Q to zero.</b></font></span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><b>3. For each episode:</b></font></span></div><blockquote><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><b>Select a random initial state.</b></font></span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><b>Do While the goal state hasn't been reached.</b></font></span></div><ul><li><font color="#AD0000" style="font-size: 12pt;"><b>Select one among all possible actions for the current state.</b></font></li><li><font color="#AD0000" style="font-size: 12pt;"><b>Using this possible action, consider going to the next state.</b></font></li><li><font color="#AD0000" style="font-size: 12pt;"><b>Get maximum Q value for this next state based on all possible actions.</b></font></li><li><font color="#AD0000" style="font-size: 12pt;"><b>Compute: Q(state, action) = R(state, action) + Gamma * Max[Q(next state, all actions)]</b></font></li><li><font color="#AD0000" style="font-size: 12pt;"><b>Set the next state as the current state.</b></font></li></ul><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><b>End Do</b></font></span></div></blockquote><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><b>End For</b></font></span></div></blockquote></div><div><font style="font-size: 16pt;"><b>The purpose of the training is to enhance the 'brain' of our agent, represented by matrix Q.</b></font></div></span>
</div></body></html> 